package leetcode;

import java.util.HashMap;
import java.util.Map;

public class ContinuousSubarraySum {

	public static void main(String[] args) {
		ContinuousSubarraySum object = new ContinuousSubarraySum();
		int[] nums = {0, 0};
		int k = 0;
		System.out.println(object.checkSubarraySum_2(nums, k));
	}
	
	//判断连续的子数组的和是否有k的倍数
	//所以我们大于k就不能移动left指针了
	
	//这道题的边界条件之多...
	//首先就是k * n = sum
	//而k和n的要求是整数，也就是n可以为0，那么对于所有的k而言，0都是满足条件的
	//还有k为负....
	//...太多边界条件了
    public boolean checkSubarraySum(int[] nums, int k) {
        if(nums == null || nums.length <= 0){
        	return false;
        }
        if(k < 0){
            k = -k;
        }
        
        int length = nums.length;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < length; i++){
        	if(nums[i] < min){
        		min = nums[i];
        	}
        	sum += nums[i];
        }
        if(sum < k || min > k){
        	return false;
        }
        
        if(sum == k && length >= 2){
        	return true;
        }
        int left = 0; 
        int right = 0;
        int cur = nums[0];
        
        //只要有和为0的，我们就返回0
        while(right < nums.length){
        	if(cur == 0){
        		if(right - left >= 1){
        			System.out.println("is there" + right + " " + left);
        			return true;
        		}else{
        			right++;
        			if(right < length){
            			cur += nums[right];
            		}
        		}
        	}else if(cur > k){
        		cur -= nums[left++];
        	}else{
        		right++;
        		if(right < length){
        			cur += nums[right];
        		}
        	}
        }
        boolean[][] dp = new boolean[length][k];
        dp[length - 1][nums[nums.length - 1] % k] = true;
        
        for(int i= length - 2; i >= 0; i--){
        	int mod = nums[i] % k;
        	for(int j = 0; j < k; j++){
        		if(dp[i + 1][j]){
        			dp[i][(j + mod) % k] = true;
        		}
        	}
        	dp[i][nums[i] % k] = true;
        }
        
//        for(int i = 0; i < length; i++){
//        	for(int j = 0; j < k; j++){
//        		System.out.print(dp[i][j] + " ");
//        	}
//        	System.out.println();
//        }
        
        while(right < nums.length){
        	if(cur % k == 0){
        		return true;
        	}else if(cur > k){
        		System.out.println("is this : " + (cur % k));
        		if(right < length - 1 && dp[right + 1][k - cur % k]){
        			return true;
        		}else{
        			cur -= nums[left++];
        		}
        	}else{
        		right++;
        		if(right < length){
        			cur += nums[right];
        		}
        	}
        }
        return false;
    }
    
    //我们先看看当求和为k的时候是怎么处理的
    public int maxSubArray(int[] nums, int k) {
        if(nums == null || nums.length <= 0){
        	return 0;
        }
        int left = 0; 
        int right = 0;
        int cur = nums[0];
        int res = 0;
        while(right < nums.length){
        	if(cur == k){
        		int curLength = right - left + 1;
        		if(curLength > res){
        			res = curLength;
        		}
        		cur -= nums[left++];
        	}else if(cur > k){
        		cur -= nums[left++];
        	}else{
        		right++;
        		if(right < nums.length){
        			cur += nums[right];
        		}
        	}
        }
        return res;
    }
    
    
    //others code
    //左程云书中的有正有负数组和为sum的应用
    public boolean checkSubarraySum_2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);
        int runningSum = 0;
        for (int i = 0; i < nums.length; i++) {
            runningSum += nums[i];
            //如果k等于0的情况，只要两个连续的0就可以了
            //由于我们之前已经将0加入了，if为false，但是map并没有put新的元素，所以0， 0是满足的
            //再比如0 1 0，到1的时候sum已经变1了，不会再进行查找0，所以使false，满足边界条件
            if (k != 0) runningSum %= k; 
            //原题是寻找target - nums[i]
            //这里我们只需要查找多余的余数的那一部分
            Integer prev = map.get(runningSum);
            
            if (prev != null) {
            	//如果[prev + 1...i]有两个元素
                if (i - prev > 1) {
                    return true;
                }
            }else {
                map.put(runningSum, i);
            }
        }
        return false;
    }
}
